home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / Puz02 / oshidori.c < prev    next >
C/C++ Source or Header  |  2000-06-28  |  3KB  |  132 lines
  1. /*
  2.  * oshidori.c : パズル「おしどり」の解法
  3.  *
  4.  *              Copyright (C) 2000 by Makoto Hiroi
  5.  *
  6.  */
  7. /*
  8.  
  9.   黒白黒白黒白空空 -> 黒黒黒白白白空空
  10.  
  11.   動かせる駒はペア単位である
  12.  
  13. */
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include <string.h>
  17.  
  18. #define TRUE  1
  19. #define FALSE 0
  20. #define S     0
  21. #define B     1
  22. #define W     2
  23. #define SIZE  8
  24.  
  25. /* 状態の最大値 */
  26. #define MAX_STATE 140
  27.  
  28. /* 状態 */
  29. char  state[MAX_STATE + 1][SIZE];    /* +1 はワーク領域 */
  30. char  space_postion[MAX_STATE];
  31. short prev_state[MAX_STATE];
  32.  
  33. /* 初期状態 */
  34. char initial_state[SIZE] = {
  35.   B, W, B, W, B, W, S, S
  36. };
  37.  
  38. /* 最終状態 */
  39. char final_state[SIZE] = {
  40.   B, B, B, W, W, W, S, S
  41. };
  42.  
  43. /* 手順の表示 */
  44. void print_answer( int n )
  45. {
  46.   int i;
  47.   if( n != 0 ) print_answer( prev_state[n] );
  48.   for( i = 0; i < SIZE; i++ ){
  49.     switch( state[n][i] ){
  50.     case S:
  51.       printf("空 "); break;
  52.     case B:
  53.       printf("黒 "); break;
  54.     case W:
  55.       printf("白 "); break;
  56.     }
  57.   }
  58.   printf("\n");
  59. }
  60.  
  61. /* 同じ状態をチェックする */
  62. int check_same_state( int n )
  63. {
  64.   /* とりあえず単純な線形探索 */
  65.   int i;
  66.   for( i = 0; i < n; i++ ){
  67.     if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
  68.   }
  69.   return FALSE;
  70. }
  71.  
  72. /* 番人を使う方法 */
  73. int check_same_state1( int n )
  74. {
  75.   int i = 0;
  76.   while( memcmp( state[i], state[n], SIZE ) ) i++;
  77.   return (i != n) ? TRUE : FALSE;
  78. }
  79.  
  80. /* 石の移動 */
  81. void move_stone( int front, int rear, int dest )
  82. {
  83.   int j = space_postion[front];
  84.   memcpy( state[rear], state[front], SIZE );
  85.   state[rear][j] = state[front][dest];
  86.   state[rear][j + 1] = state[front][dest + 1];
  87.   state[rear][dest] = S;
  88.   state[rear][dest + 1] = S;
  89.   space_postion[rear] = dest;
  90.   prev_state[rear] = front;
  91. }
  92.  
  93. /* 探索関数 */
  94. void search( void )
  95. {
  96.   int front = 0, rear = 1;
  97.   /* 初期化 */
  98.   memcpy( state[0], initial_state, SIZE );
  99.   prev_state[0] = -1;
  100.   space_postion[0] = 6;
  101.   while( front < rear ){
  102.     int i;
  103.     /* 移動 (0 から 6 までチェック) */
  104.     for( i = 0; i < SIZE - 1; i++ ){
  105.       if( state[front][i] && state[front][i + 1] ){
  106.     /* 移動可能 */
  107.     move_stone( front, rear, i );
  108.     /* チェックする */
  109.     if( !memcmp( state[rear], final_state, SIZE ) ){
  110.       /* 解けた */
  111.       print_answer( rear );
  112.       printf("状態数 %d 個\n", rear );
  113.       return;
  114.     } else if( !check_same_state1( rear ) ){
  115.       /* 同じ状態はない */
  116.       rear++;
  117.     }
  118.       }
  119.     }
  120.     front++;
  121.   }
  122. }
  123.  
  124. int main()
  125. {
  126.   search();
  127.   return 0;
  128. }
  129.  
  130. /* end of file */
  131.  
  132.